package stack.medium;

import java.util.Stack;


/**
 * 行星碰撞
 * 示例 1：
 *
 * 输入：asteroids = [5,10,-5]
 * 输出：[5,10]
 * 解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。
 * 示例 2：
 *
 * 输入：asteroids = [8,-8]
 * 输出：[]
 * 解释：8 和 -8 碰撞后，两者都发生爆炸。
 * 示例 3：
 *
 * 输入：asteroids = [10,2,-5]
 * 输出：[10]
 * 解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。
 * 示例 4：
 *
 * 输入：asteroids = [-2,-1,1,2]
 * 输出：[-2,-1,1,2]
 * 解释：-2 和 -1 向左移动，而 1 和 2 向右移动。 由于移动方向相同的行星不会发生碰撞，所以最终没有行星发生碰撞。
 *
 * 链接：https://leetcode-cn.com/problems/asteroid-collision
 */
public class AsteroidCollision_735 {

    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        for (int asteroid : asteroids) {
            if (asteroid > 0)
                stack.push(asteroid);
            else{
                while (!stack.isEmpty() && stack.peek() > 0 && stack.peek() < (-asteroid))
                    stack.pop();
                if (!stack.isEmpty() && stack.peek() == -asteroid)
                    stack.pop();
                else if (stack.isEmpty() || stack.peek() < 0)
                    stack.push(asteroid);
            }
        }

        int[] arr = new int[stack.size()];
        int n = stack.size();
        for (int i = n - 1; i >= 0; i--) {
             arr[i] = stack.pop();
        }
        return arr;
    }
}
